/**
 * @(#) LongestIncreasingSequence.java Apr 4, 2010 8:19:11 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package old;

/**
 * Class <code>LongestIncreasingSequence</code>
 * 
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Apr 4, 2010 8:19:11 PM
 * 
 */
public class

LongestIncreasingSequence
{
	// if value does not appear into the array, but 
	// arr[0] < value <arr[size] the function returns index,
	// arr[index-1] < value < arr[index]
	// if value<arr[0] the function returns zero 
	// if value>arr[end] the function returns end+1
	public static int binarySearchNear(int[] arr, int end, int value)
	{
		int low = 0, high = end;
		if (value < arr[0])
			return 0;
		if (value > arr[end])
			return end + 1;
		while (low <= high)
		{
			int middle = (low + high) / 2;
			if (low == high)
			{
				if (arr[low] == value)
					return low;
				else

					return low;
			} else
			{
				if (arr[middle] == value)
				{// value was found
					return middle;
				}// value suppose to be left
				if (value < arr[middle])
				{
					high = middle;
				} // value suppose to be right
				else
				{
					low = middle + 1;
				}
			}
		}
		return -1;
	}

	// // array contains different integer numbers,assumption: arr
	// calculation of the length of largest increment subsequence

	public static int LISLength(int[] arr)
	{
		int size = arr.length;
		int d[] = new

		int[size];
		d[0] = arr[0];
		int end = 0;
		for (int i = 1; i < size; i++)
		{
			int index = binarySearchNear(d, end, arr[i]);
			if (index <= end)
				d[index] = arr[i];
			else
			{
				end++;
				d[end] = arr[i];
			}
		}
		return end + 1;
	}

	// array contains integer different numbers,assumption: arr.length>2//
	// calculation of the length of largest increment subsequence

	public static int[] LIS(int[] arr)
	{
		int size = arr.length;
		int mat[][] = new int[size][size];
		int d[] = new int[size];
		mat[0][0] = arr[0];
		d[0] = arr[0];
		int end = 0;
		for (int i = 1; i < size; i++)
		{
			int index = binarySearchNear(d, end, arr[i]);
			mat[index][index] = arr[i];
			for (int j = 0; j < index; j++)
				mat[index][j] = mat[index - 1][j];
			for (int j = 0; j < index; j++)
				d[j] = mat[index - 1][j];
			d[index] = arr[i];
			if (index > end)
				end++;
		}
		int ans[] = new

		int[end + 1];
		for (int j = 0; j <= end; j++)
			ans[j] = mat[end][j];
		return ans;
	}

	public static void main(String[] args)
	{
		int[] arr =
		{ 1,-1,2,-3,4,-5,6,-7};
		System.out.println(LISLength(arr));
		int[] d = LIS(arr);
		System.out.println(d.length);
		
		for(int i : d)
		{
			System.out.print(i + " ");
		}
		System.out.println("");
	}
}